Search results for "Atomic formula"

showing 2 items of 2 documents

Algebre, Gettoni, Enunciati

2021

The paper aims at describing some differences between the formal languages of Mathematics and the features of Natural Language

Algebra Atomic Formula Utterance Everyday Discourse Logic
researchProduct

Local Normal Forms for First-Order Logic with Applications to Games and Automata

1999

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata mode…

General Computer ScienceLogical equivalenceautomataComputer scienceOf the formMathematical proofMonadic predicate calculusTheoretical Computer ScienceCombinatoricslocalityDeterministic automatonDiscrete Mathematics and CombinatoricsMathematicsgamesDiscrete mathematicsPredicate logiclcsh:MathematicsLocalityAtomic formulaexistential monadic second-order logiclcsh:QA1-939AutomatonFirst-order logic[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESAutomata theoryFirst-order logicDiscrete Mathematics & Theoretical Computer Science
researchProduct